"""

实现 FreqStack，模拟类似栈的数据结构的操作的一个类。

FreqStack 有两个函数：

push(int x)，将整数 x 推入栈中。
pop()，它移除并返回栈中出现最频繁的元素。
如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。

"""

class FreqStack:
	"""
	用什么来记录频率？要求可以快速获得最高的频率
	如何维护这个栈？
	看了题解后会发现，这个结构是精心设计的
	"""
    def __init__(self):
        
        self.num2freq = collections.Counter()  # 元素 到 其频率 的映射
        self.freq2num = collections.defaultdict(list) # 频率 到 拥有该频率的元素 的映射
        self.maxfreq = 0 # 当前的最高频率


    def push(self, val: int) -> None:
        self.num2freq[val] = self.num2freq[val] + 1 # 该元素增加一个 自然其频率也要增加
        f = self.num2freq[val]
        
        self.maxfreq = max(f, self.maxfreq) # 维护最大频率
        
        self.freq2num[f].append(val)
        """
        假设一个元素 val 其频率从0增加到5 那么他的拥有的频率也是0-5（同时拥有的）
        频率5的组中没有val了，频率4的组中还有
        """

    def pop(self) -> int:
        
        x = self.freq2num[self.maxfreq].pop() 
        """
        从频率最大的组中弹出元素
        因为freq2num采取的是stack 后面进的靠近栈顶 也符合要求
        """
        self.num2freq[x] -= 1
        if not self.freq2num[self.maxfreq]: 
            self.maxfreq -= 1
        """
        如果该频率没有元素了 那么maxfreq就退1 因为一个元素到达maxfreq 肯定也会在maxfreq-1留下名字
        """
        
        return x



# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()